package com.hejjon;

import java.util.LinkedList;

/**
 *  3. 无重复字符的最长子串
 * Created by caoshi at 20:45 2021-10-15
 */
public class LongestSubstring {

    public static void main(String[] args) {
        String s = "dvdf";
        LongestSubstring ls = new LongestSubstring();
        int i = ls.lengthOfLongestSubstring(s);
        System.out.println(i);

    }



    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        LinkedList<Character> list = new LinkedList<>();
        int max = 0;
        for (int i = 0; i < chars.length; i++) {

            // 遇到已经有的字符串, 就从最开始位置开始删除直到当前这个字符(包含)
            if (list.contains(chars[i])) {
                remove2(list, chars[i]);
            }

            list.addLast(chars[i]);

            if (list.size() > max) {
                max = list.size();
            }

        }

        return max;
    }


    private void remove(LinkedList<Character> src, Character c) {
        Character remove = src.removeFirst();

        if (!remove.equals(c)) {
            remove(src, c);
        }
    }

    /**
     * 移除从首位开始到指定字符之间(含这个指定字符)的所有字符
     * @param src
     * @param c
     */
    private void remove2(LinkedList<Character> src, Character c) {
        int cindex = src.indexOf(c);
        LinkedList<Character> rem = new LinkedList<>();
        for (int i = 0; i < cindex + 1; i++) {
            rem.add(src.get(i));
        }
        src.removeAll(rem);
    }


}
